#include <vector>
#include <iostream> 
using namespace std;
namespace fuh{

    //仿函数
    template <class T>
    class greater
    {
        public:
        bool operator()(const T& a, const T& b)
        {
            return a < b;
        }
    };



    template<class T,class Container=std::vector<T>,class Compare = greater<T>>
    class priority_queue{
        Container m_c;
        Compare compare;
    public:
        template <class InputIterator>
        priority_queue(InputIterator first,InputIterator last)
        :m_c(first,last)
        {
            for(int i=(m_c.size()-2)/2;i>=0;i--)
            {
                adjust_down(i);
            }
        }
        priority_queue(){}
        ~priority_queue(){}

        void adjust_up(int child){
            int parent =(child-1)/2;
            while(child>0 )
            {
    
                if(compare(m_c[parent],m_c[child]))
                {
                    swap(m_c[parent],m_c[child]);
                    child = parent;
                    parent = (child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        void adjust_down(int parent)
        {
            int child = 2*parent+1;
            while(child<m_c.size())
            {
                if(child+1<m_c.size() && compare(m_c[child],m_c[child+1]))
                {
                    child++;
                }
                if(compare(m_c[parent],m_c[child]))
                {
                    swap(m_c[parent],m_c[child]);
                }
                else
                {
                    break;
                }
                parent = child;
                child = 2*parent+1;
            }
        }
        void push(const T& x)
        {
            m_c.push_back(x);
            adjust_up(m_c.size()-1);
        }
        void pop()
        {
            swap(m_c[0],m_c[m_c.size()-1]);
            m_c.pop_back();
            adjust_down(0);
        }
        const T& top() const
        {
            return m_c[0];
        }
        bool empty() const
        {
            return m_c.empty();
        }
        size_t size() const
        {
            return m_c.size();  
        }
    };
    void test1()
    {
        priority_queue<int> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        while(!q.empty())
        {
            cout<<q.top()<<" ";
            q.pop();
        }
        cout<<endl;

    }
};


int main()
{
    fuh::test1();
    return 0;
}